public class recusion {
   /* //按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)
    public static void print(int num){
        if(num > 9){//85
            print(num / 10);//8
        }
        System.out.println(num % 10);//5
    }

    public static void main(String[] args) {
        print(1234);
    }*/


  /*  //递归求 1 + 2 + 3 + ... + 10
    public static int sum(int num){
        if(num == 1){
            return 1;
        }
        return num + sum(num-1);
    }

    public static void main(String[] args) {
        System.out.println(sum(10));
    }*/


/*
    //写一个递归方法，输入一个非负整数，返回组成它的数字之和.
    // 例如，输入 1729, 则应该返回1+7+2+9，它的和是19

    public static int sum(int num){
        if(num < 10){
            return num;
        }
        return num % 10 + sum(num / 10);//17
    }

    public static void main(String[] args) {
        System.out.println(sum(1729));
    }
*/

    //求斐波那契数列的第 N 项
   /* public static int fib(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        System.out.println( fib(3));
    }*/

    public static int fib2(int n) {
        if (n == 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        }
        int f1 = 0;
        int f2 = 1;
        int f3 = -1;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;//3--2
            f1 = f2;//1--1
            f2 = f3;//2--1
            //0 1 1 2 3 5 8
        }
        return f3;
    }

    public static void main(String[] args) {
        System.out.println(fib2(5));
    }



}
